
class Solution2 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static Node copyRandomList(Node head) {
        if (head == null) return null;
        //先复制每个节点一份跟在每一个节点的后面
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        //然后给每个复制节点的random赋值
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = node.next;
            //通过node找到所复制的random
            newNode.random = node.random == null ? null : node.random.next;
        }
        Node newHead = head.next;
        //最后把所复制的节点从原链表拆分下来连成单独的所求的复制链表
        for (Node node = head; node != null; node = node.next) {
            Node newNode = node.next;
            node.next = node.next.next;
            newNode.next = newNode.next == null ? null : node.next.next;
        }
        return newHead;
    }
}